 %\begin{document}
\setcounter{chapter}{1}
\setcounter{chapter}{1}
\chapter{Kĩ thuật phân hoạch, chia để trị và một số ứng dụng}
Phân hoạch(\textit{partitioning}) và chia để trị(\textit{divide-and-conquer}) là hai kỹ thuật cơ bản để xây dựng một chương trình song song. Hai kĩ thuật này có liên quan tới nhau. Trong kĩ thuật phân hoạch, bài toán được chia thành các phần riêng lẻ và mỗi phần được tính toán riêng. Kĩ thuật chia để trị thường áp dụng kĩ thuật phân hoạch trong phép đệ quy để chia liên tục bài toán thành các phần nhỏ hơn trước khi giải quyết các phần nhỏ hơn và hợp các kết quả lại.
\section{Kĩ thuật phân hoạch, chia để trị}
\subsection{Các chiến lược phân hoạch}
Phân hoạch đơn giản là chia bài toán thành các phần nhỏ. Tuy nhiên, các công thức phân hoạch đều yêu cầu kết quả của các phần nhỏ hợp lại để đạt được kết quả mong muốn.\\
\indent Kĩ thuật phân hoạch có thể được áp dụng trong dữ liệu của chương trình, tức là chia nhỏ dữ liệu và thao tác trên các dữ liệu đã chia một cách đồng thời. Việc này được gọi là chia nhỏ dữ liệu(\textit {data partitioning}) hay sự phân nhỏ miền(\textit{domain decomposition}).\\
\indent Kĩ thuật phân hoạch cũng có thể được áp dụng trong các chức năng của chương trình, tức là chia bài toán thành các chức năng độc lập và thực hiện các chức năng một cách đồng thời. Việc này được gọi là phân nhỏ chức năng(\textit{functional decomposition})\\
\subsubsection{Chia nhỏ dữ liệu}
Chia nhỏ dữ liệu là một phương pháp được dùng phổ biến và rộng rãi trong viêc tạo sự thực hiện cùng nhau trong một thuật toán thao tác trên một cấu trúc dữ liệu lớn. Trong phương pháp này, việc chia nhỏ dữ liệu được thực hiện theo hai bước: trong bước thứ nhất, chia nhỏ dữ liệu của các phép toán được thực hiện; trong bước thứ hai, phân hoạch dữ liệu này được dùng để tạo ra một phân hoạch của các phép toán váo trong các tác vụ.\\
\indent Có nhiều cách có thể để chia nhỏ dữ liệu. Nhìn chung chúng ta phải khảo sát và đánh giá tất cả các cách có thể để xác định cách chia nhỏ nào đạt được sự chia nhỏ tính toán hiệu quả và tự nhiên.
\paragraph{Chia nhỏ dữ liệu ra}Trong rất nhiều phép tính, mỗi phần của dữ liệu ra (kết quả) có thể được tính độc lập với nhau theo một hàm đầu vào. Trong các phép toán này, việc chia nhỏ kết quả tự động tạo ra một phép chia bài toán thành các tác vụ, trong đó mỗi tác vụ thực hiện công việc tính toán một phần kết quả.\\
\indent Ví dụ 1: Phép nhân 2 ma trận A và B cỡ $n\times n$ thành ma trận C. Một phép chia phép tính này vào trong 4 tác vụ. Mỗi ma trận được xem như hợp thành từ 4 ma trận con được định nghĩa bằng cách tách đôi các hàng và các cột. 4 ma trận con của ma trận C được tính bởi 4 tác vụ một cách độc lập (xem hình 1.8).
\begin{figure}[ht]
\centering
\includegraphics{chiadulieu1.jpg}
\caption{\textit{(a) Chia các ma trận vào và ra thành các ma trận cỡ $2\times2$. (b) Sự phân chia của phép toán nhân ma trận thành 4 tác vụ dự trên việc phân nhỏ các ma trận trong (a).}}\label{fig:Hình}
\end{figure}
\\ Việc phân chia dữ liệu và việc phân chia bài toán thành các tác vụ là khác nhau. Việc phân chia dữ liệu hỗ trợ việc phân chia bài toán thành các tác vụ. Với một phép chia dữ liệu không tồn tại duy nhất một cách phân chia bài toán thành các tác vụ. Hình 1.8 chỉ ra 2 cách phân chia phép nhân ma trân thành 8 tác vụ phù hợp với cùng một phép chia dữ liệu.
\begin{figure}[ht]
\centering
\includegraphics{chiadulieu2.jpg}
\caption{\textit{Hai ví dụ về sự phân chia phép nhân ma trận thành 8 tác vụ.}}\label{fig:Hình}
\end{figure}
\paragraph{Chia nhỏ dữ liệu vào}Mỗi tác vụ được tạo ra cho một phần của dữ liệu vào và các tác vụ này có thể thực hiện các phép toán có thể trên các dữ liệu cục bộ này. Chú ý rằng các kết quả có được từ các tác vụ thực hiện trên các phần dữ liệu vào có thể không phải là kết quả trực tiếp của bài toán gốc, khi ấy thì các kết quả này cần được kết hợp lại.\\
\indent Ví dụ 2: Tính tổng của một dãy số gồm $n$ phần tử $x_0,x_1,...,x_(n-1)$. Chúng ta có thể chia dãy thành $m$ phần, mỗi phần có $n/m$ phần tử, $(x_0,\ldots,x_{n/m-1})$, $(x_n/m,\ldots,x_{2n/m-1})$, ..., $(x_{(m-1)n/m},\ldots,x_{n-1})$ và sử dụng $m$ bộ xử lý (hoặc $m$) tiến trình để cộng các số của mỗi phần để tạo ra các tổng thành phần. Cuối cùng $m$ tổng thành phần này cần được cộng lại để đưa ra tổng của dãy. (Hình...)
\begin{figure}[ht]
\centering
\includegraphics[scale=0.75]{chiadulieu6.jpg}
\caption{\textit{Chia nhỏ một dãy các số thành nhiều phần và tính tổng các phần}}\label{fig:Hình}
\end{figure}
\paragraph{Chia nhỏ dữ liệu trung gian}Các thuật toán có cấu trúc là nhiều bước tính toán, ví như kết quả của bước tính toán này có thể là dữ liệu vào của bước tính tiếp theo. Sự phân chia một thuật toán như thế có thể đạt được bằng cách phân chia dữ liệu vào hoặc ra của các bước tính trung gian của thuật toán. Việc phân chia dữ liệu trung gian đôi khi có thể đạt độ song song cao hơn việc phân chia dữ liệu ra hoặc kết quả của bài toán. \\
\indent Ví dụ 3: Để tăng độ song song của bài toán nhân ma trận trong ví dụ 1, chúng ta sẽ đưa vào 1 giai đoạn trung gian, trong đó 8 tác vụ tính các ma trận tích riêng từng cái và lưu vào một ma trận tạm thời 3 chiều D, hình 1.9. Ma trận con $D_{k,i,j}$ là tích của ma trận con $A_{i,k}$ và $B_{k,j}$. 
\begin{figure}[ht]
\centering
\includegraphics[scale=0.75]{chiadulieu3.jpg}
\caption{\textit{Phép nhân ma trận A và B với việc chia nhỏ ma trận trung gian 3 chiều D.}}\label{fig:Hình}
\end{figure}

\indent Việc phân nhỏ ma trận trung gian $D$ đưa đến một cách phân chia bài toán nhân ma trận thành 8 tác vụ, hình 1.10. Sau bước nhân, một bước cộng ma trận không đắt có thể tính toán kết quả ma trận $C$. Tất cả các ma trận con $D_{*,i,j}$ có chỉ số thứ hai $i$và thứ ba $j$ giống nhau được cộng với nhau cho ra $C_{i,j}$. Tám tác được đánh số từ 1 đến 8 trong hình... thực hiện $O(n^3/8)$ công việc mỗi tác vụ nhân các ma trận con cỡ $n/2\times n/2$ của ma trận $A$ và $B$. Sau đó, bốn tác vụ được đánh số từ 9 đến 12 mỗi tác vụ sử dụng $O(n^2/4)$ thời gian để cộng các ma trận con phù hợp cỡ $n/2\times n/2$ của ma trận trung gian $D$ để đưa ra kết quả cuối cùng, ma trận $C$. 
\begin{figure}[ht]
\centering
\includegraphics{chiadulieu4.jpg}
\caption{\textit{Cách phân chia bài toán nhân ma trận dựa trên việc chia nhỏ dữ liệu ma trận 3 chiều trung gian.}}\label{fig:Hình}
\end{figure}
Đây là đồ thị phụ thuộc tác vụ phù hợp với phép chia nhỏ trên.
\begin{figure}[ht]
\centering
\includegraphics{chiadulieu5.jpg}
\caption{\textit{Đồ thị phụ thuộc tác vụ của phép chia nhỏ hình...}}\label{fig:Hình}
\end{figure}
\subsubsection{Chia nhỏ theo chức năng}
\subsection{Chia để trị}
Cách tiếp cận chia để trị(\textit{divide-and-conquer}) được đặc trưng bằng việc chia một bài toán thành các bài toán nhỏ hơn có cùng dạng với bài toán lớn sử dụng phương pháp đệ quy. Phương pháp đệ quy sẽ tiếp tục chia bài toán thành các tác vụ nhỏ hơn cho tới khi các tác vụ không thể nhỏ hơn được nữa. Sau đó các tác vụ đơn giản nhất được thực hiện và nối các kết quả với nhau để thực các tác vụ lớn hơn, cho đến khi thu được kết quả cuối cùng.\\
\indent JaJa(1992) đã phân biệt giữa phương pháp chia để trị và phân hoạch dựa vào công việc chính của mỗi phương pháp. Ông gọi là phương pháp chia để trị khi công việc chính là việc tổng hợp các kết quả, và gọi là phân hoạch khi công việc chính là chia nhỏ bài toán. Ở đây, chúng ta sẽ sử dụng thuật ngữ chia để trị bất cứ khi nào việc chia nhỏ còn được tiếp tục trên các bài toán nhỏ hơn.
\subsubsection{Ví dụ}
Tính tổng $S$ của dãy gồm $n$ số: $S=\sum_{i=0}^{n-1}x_i$.\\
Một định nghĩa đệ quy để cộng danh sách số(s) gồm $n$ phần tử được thể hiện như sau:\\
\hspace*{0.3in} Int add(int ${}^{*}$s)\\ 
\hspace*{0.3in} \{\\
\hspace*{0.5in} if (number(s) $=<$ 2) return (n1$+$n2);\\
\hspace*{0.5in} else \{\\
\hspace*{0.6in} divide(s, s1, s2); \hspace{0.3in} ${/}^{*}$Chia s thành 2 phần s1, s2 ${}^{*}/$\\
\hspace*{0.6in} part$\_$sum1 $=$ add(s1); \hspace{0.2in}${/}^{*}$Các lời gọi đệ quy để cộng các danh sách con${}^{*}/$\\
\hspace*{0.6in} part$\_$sum2 $=$ add(s2);\\
\hspace*{0.6in} return (part$\_$sum1$+$part$\_$sum2);\\
\hspace*{0.5in}\}\\
\hspace*{0.3in} \}\\
\indent Trong tất cả các định nghĩa đệ quy, một phương thức phải kết thúc được lời gọi đệ quy khi việc chia nhỏ không thể thực hiện được nữa. Trong mã lệnh trên, number(s) trả lại số các số trong danh sách s. Nếu có 2 số trong danh sách, hai số đó được gọi là n1 và n2. Nếu có 1 số trong danh sách thì số đó được gọi là n1, n2$=$0. Nếu không có số nào trong danh sách, thì n1$=$n2$=$0. Lời gọi đệ quy trong mã lệnh trên sẽ kết thúc trong các trường hợp có 0, 1 hoặc 2 số trong danh sách.\\
\indent Khi mỗi phép chia tạo thành 2 phần, thì kĩ thuật chia để trị đệ quy sẽ có dạng một cây nhi phân hoàn chỉnh. Với các thể hiện tuần tự, tại mỗi thời điểm ta chỉ thăm được một nút của cây. Nhưng với thể hiện song song, tại một thời điểm ta có thể thăm nhiều nút của cây một cách đồng thời bằng cách thực hiện như sau:
\begin{itemize}
\item Thực hiện việc chia dữ liệu trong bài toán tính tổng dãy số $x_0, x_1,\ldots, x_{n-1}$, và sử dụng 8 bộ xử lý $P_0, P_1,\ldots, P_8$. Tại mỗi giai đoạn, mỗi bộ xử lý sẽ giữ một nửa danh sách và gửi nửa còn lại cho bộ xử lý khác. Đầu tiên, $P_0$ giao tiếp với $P_4$, gửi một nửa dữ liệu tới $P_4$. Sau đó, $P_0$ và $P_4$ lại gửi một nửa dữ liệu của mình cho $P_2$ và $P_6$ một cách tương tự. Cuối cùng, $P_0, P_2, P_4$ và $P_6$ gửi một nửa dữ liệu của mình cho $P_1, P_3, P_5$ và $P_7$ một cách tương tự. Mỗi danh sách trong giai đoạn cuối sẽ có $n/8$ số hoặc $n/p$ số trong trường hợp sử dụng $p$ bộ xử lý.
\begin{figure}[!ht]
\centering
\includegraphics[scale=0.75]{chiadetri1.jpg}
\caption{\textit{Chia nhỏ một danh sách thành các phần}}\label{fig:Hình}
\end{figure}
\item Việc liên kết để tính tổng của các tổng thành phần có thể được thực hiện như hình...Khi các tổng thành phần đã được tính, mỗi tiến trình được đánh số lẻ sẽ gửi kết quả của mình cho các tiến trình được đánh số chẵn liền kề nó. Đó là, $P_1$ gửi kết quả của mình tới $P_0$, $P_3$ gửi tới $P_2$, $P_5$ gửi tới $P_4$, và $P_7$ gửi tới $P_6$. Các bộ xử lý được đánh số chẵn sau đó sẽ cộng kết quả nhận được với tổng thành phần của mình và gửi kết quả lên trên. Quá trình tiếp tục cho tới khi $P_0$ có được kết quả cuối cùng.
\begin{figure}[!ht]
\centering
\includegraphics[scale=0.75]{chiadetri2.jpg}
\caption{\textit{Tính tổng thành phần}}\label{fig:Hình}
\end{figure}
\end{itemize}
\subsubsection{Phân tích thuật toán}
Giả thiết $n$ là lũy thừa của 2, và sử dụng $p$ bộ xử lý. Thời gian thiết lập truyền thông $t_{startup}$ không được tính trong các bước.
\begin{itemize}
\item Thời gian truyền thông
\begin{itemize}
\item Trong giai đoạn chia nhỏ, ta phải thực hiện $\log_{}p$ bước chia. Thời gian truyền thông của giai đoạn này là
\[t_{comm1}=\frac{n}{2}t_{data}+\frac{n}{4}t_{data}+\cdots+\frac{n}{p}t_{data}=\frac{n(p-1)}{p}t_{data}\]
trong đó, $t_{data}$ là thời gian để chuyển một từ dữ liệu.
\item Trong giai đoạn hợp kết quả, thời gian truyền thông được tính tương tự nhưng mỗi thông điệp chỉ chứa một dữ liệu.\[t_{comm2}=t_{data}\log_{}p\]
\end{itemize}
Vậy tổng thời gian truyền thông của thuật toán là:\[t_{comm}=t_{comm1}+t_{comm1}=\frac{n(n-p)}{n}t_{data}+t_{data}\log_{}p\]
hay độ phức tạp thời gian là $O(n)$ với $p$ là hằng số.
\item Thời gian tính toán\\
Khi kết thúc giai đoạn chia nhỏ, việc tính tổng của $n/p$ số được thực hiện ở mỗi bộ xử lý. Và trong giai đoạn hợp kết quả mỗi bước chỉ thực hiện một phép cộng. Thời gian tính toán của thuật toán:
\[t_{comp}=\frac{n}{p}+ logp\]
hay độ phức tạp thời gian là $O(n)$ khi $p$ là hằng số. Với $n$ lớn và $p$ là biến thì ta sẽ lấy độ phức tạp thời gian là $O(n/p)$.
\end{itemize}
Tổng thời gian thực hiện song song của thuật toán là 
\[t_p=\frac{n(n-p)}{p}t_{data}+t_{data}\log_{}p+\frac{n}{p}+\log_{}p\]

\subsection{Chia để trị $m$-nhánh}
Kĩ thuật chia để trị cũng có thể được áp dụng vào các bài toán mà khi một tác vụ được chia nhỏ thành nhiều hơn hai phần ở mỗi bước. Ví dụ một tác vụ được chia nhỏ thành bốn phần, định nghĩa đệ quy tuần tự có thể là\\
\hspace*{0.3in} Int add(int ${}^{*}$s)\\ 
\hspace*{0.3in} \{\\
\hspace*{0.5in} if (number(s) $=<$ 4) return ($n1+n2+n3+n4$);\\
\hspace*{0.5in} else \{\\
\hspace*{0.6in} divide(s, s1, s2, s3, s4); \hspace{0.3in} ${/}^{*}$Chia s thành 2 phần s1, s2, s3, s4 ${}^{*}/$\\
\hspace*{0.6in} part$\_$sum1 $=$ add(s1); \hspace{0.2in}${/}^{*}$Các lời gọi đệ quy để cộng các danh sách con${}^{*}/$\\
\hspace*{0.6in} part$\_$sum2 $=$ add(s2);\\
\hspace*{0.6in} part$\_$sum3 $=$ add(s3);\\
\hspace*{0.6in} part$\_$sum4 $=$ add(s4);\\
\hspace*{0.6in} return (part$\_$sum1$+$part$\_$sum2$+$part$\_$sum3$+$part$\_$sum4);\\
\hspace*{0.5in}\}\\
\hspace*{0.3in} \}\\
Cây $m$-nhánh được hình thành nếu phép chia là phép chia nhỏ thành $m$ phần. Cây $m$-nhánh có những ứng dụng cụ thể riêng. Ví dụ, trong cây mỗi nút cha có bốn nút con, gọi là \textit{quadtree} được ứng dụng để chia các miền $2-$chiều thành bốn miền con (Hình...); \textit{octree} là cây trong đó mỗi nút cha có tám nút con được ứng dụng trong việc chia không gian $3-$chiều đệ quy (Hình...).
\begin{figure}[ht]
\centering
\includegraphics[scale=0.75]{quadtree.jpg}
\caption{\textit{Quadtree và ứng dụng để chia miền 2-chiều}}\label{fig:Hình}
\end{figure}
\begin{figure}[ht]
\centering
\includegraphics[scale=0.6]{octree.jpg}
\caption{\textit{Octree và ứng dụng để chia không gian 3-chiều}}\label{fig:Hình}
\end{figure}

\section{Một số ứng dụng trong thuật toán song song}
\subsection{Nhân hai ma trận}
Trong phần này chúng ta sẽ ứng dụng kĩ thuật chia nhỏ dữ liệu để thiết kế thuật toán song song cho bài toán nhân hai ma trận vuông dày đặc $A$ và $B$ cỡ $n\times n$, cho ra kết quả là ma trận $C$. Các thuật toán song song nhân hai ma trận trong phần này sẽ dựa trên thuật toán tuần tự thông thường nhân hai ma trận được chỉ ra ở thuật toán 1. Có nhiều thuật toán tuần tự nhân hai ma trận có độ phức tạp tuần tự tiệm cận tốt hơn nhưng để đơn giản chúng ta giả thiết thuật toán 1 là thuật toán tuần tự tốt nhất.\\
\textbf{Thuật toán 1: Thuật toán tuần tự thông thường để nhân hai ma trận cỡ $n\times n$.}\\
1.\quad procedure $MAT\_MULT (A, B, C)$\\
2.\quad begin\\
3.\qquad for $i:=0$ to $n-1$ do\\
4.\hspace{3cm} for $j:=0$ to $n-1$ do\\
5.\hspace{3cm} begin\\
6.\hspace{4cm} $C[i,j]:=0$;\\
7.\hspace{4cm} for $k:=0$ to $n-1$ do\\
8.\hspace{5cm} $C[i,j]:=C[i,j]+A[i,k]*B[k,j]$;\\
9.\hspace{3cm} endfor;\\
10.\quad end$MAT\_MULT$;\\

Giả thiết cặp phép cộng và nhân ở dòng 8 yêu cầu một đơn vị thời gian thì thời gian chạy tuần tự của thuật toán này là $n^3$.\\
\indent Một khái niệm được sử dụng nhiều trong các thuật toán nhân ma trận đó là các phép toán ma trận khối. Để thực hiện một phép toán đại số vô hướng của ma trận trên tất cả các phần tử ta thay bằng việc thực hiện phép toán đó trên các khối(các ma trận con) của ma trận ban đầu. Ví dụ, ma trận $A$ cỡ $n\times n$ có thể được thay bằng một mảng hai chiều $q\times q$ của các khối $A_{i,j} (0\leq i,j\leq q)$, trong đó mỗi khối là một ma trận con cỡ $(n/p)\times (n/q)$.\\
\indent Thuật toán 1 có thể được viết lại sử dụng các phép toán ma trận khối như sau:\\
\textbf{Thuật toán 2: Thuật toán nhân ma trận khối của hai ma trận cỡ $n\times n$ với cỡ của khối là $(n/q)\times (n/q)$.}\\
1.\quad procedure $BLOCK\_MAT\_MULT (A, B, C)$\\
2.\quad begin\\
3.\qquad for $i:=0$ to $q-1$ do\\
4.\hspace{3cm} for $j:=0$ to $q1$ do\\
5.\hspace{3cm} begin\\
6.\hspace{4cm} $fillchar(C, sizeof(C),0)$;\\
7.\hspace{4cm} for $k:=0$ to $q-1$ do\\
8.\hspace{5cm} $C[i,j]:=C[i,j]+A[i,k]*B[k,j]$;\\
9.\hspace{3cm} endfor;\\
10.\quad end $BLOCK\_MAT\_MULT$;\\
\indent Ta thấy, không chỉ kết quả cuối cùng của hai thuật toán mà tổng các phép toán cộng và nhân vô hướng được thực hiện trong hai thuật toán cũng giống hệt nhau. Cả hai thuật toán đều thực hiện $n^3$ phép cộng và nhân.\\
Một cách để song song hóa thuật toán là sử dụng $p$ tiến trình để thể hiện các khối của ma trận một cách song song băng phép chọn $\sqrt{q}=p$. Dưới đây là ba thuật toán song song tiếp cận theo cách song song hóa thuật toán 2 và sử dụng phép chia nhỏ 2-chiều.

\subsubsection{Thuật toán song song đơn giản}







\subsection{Sắp xếp theo giỏ(\textit{Bucket sort})}
Các thuật toán sắp xếp đã được nghiên cứu nhiều trong lập trình tuần tự. Hầu hết các thuật toán sắp xếp tuần tự đều dựa trên cơ sở so sánh và đổi chỗ các cặp số. Phần này chúng ta sẽ sử dụng kĩ thuật phân hoạch và chia để trị để song song hóa thuật toán sắp xếp theo giỏ(\textit{bucket sort}).\\
\indent Thuật toán bucket sort không dựa trên cơ sở so sánh và đổi chỗ, thuật toán là một phép phân hoạch một cách tự nhiên. Thuật toán bucket sort chỉ có hiệu quả khi các số ban đầu có phân bố đều trên một khoảng cho trước, giả sử từ $0$ đến $a-1$. Khoảng cho trước sẽ được chia thành $m$ khoảng nhỏ, $0$ tới $a/m-1$, $a/m$ tới $2a/m-1$,$\ldots$, và mỗi giỏ được gán để chứa các số trong khoảng đó, vậy cần có $m$ giỏ.
\subsubsection{thuật toán tuần tự}
\begin{itemize}
\item Đặt các số vào các khoảng phù hợp: Để đặt một số vào khoảng thích hợp, ta có thể so sánh số đó với các các số $a/m, 2a/m, 3a/m,\ldots$, sẽ cần nhiều $m-1$ bước so sánh để đặt được một số vào dãy thích hợp. Hoặc ta có thể chia số đó cho m, sử dụng kết quả để đặt vào các giỏ tương ứng từ $0$ đến $m-1$. Nếu $m$ là lũy thừa của 2 ta có thể sử dụng các bit trên đầu của mỗi số dưới dạng nhị phân. Trong bất kì cách nào, ta giả sử để đặt một số vào giỏ cần 1 bước. Vậy để đặt tất cả các số cần $n$ bước.
\begin{figure}[ht]
\centering
\includegraphics[scale=0.75]{bucket1.jpg}
\caption{\textit{Sắp xếp theo giỏ}}\label{fig:Hình}
\end{figure}
\item Các số trong mỗi giỏ sẽ được sắp xếp bởi một thuật toán sắp xếp tuần tự: Giả sử thuật toán sắp xếp tuần tự sử dụng để sắp ở mỗi giỏ đòi hỏi $n\log_{}n$ phép so sánh, mỗi phép so sánh tương đương với một bước tính toán. Vậy để sắp xếp $n/m$ số ở mỗi giỏ cần $n/m\log_{}{n/m}$ bước.
\item Nối các số trong giỏ đã sắp để đưa ra dãy đã sắp cuối cùng: không sử dụng tính toán.
\end{itemize}
Vậy thời gian xử lý tuần tự là
\[t_s=n+m((n/m)\log_{}{(n/m)})=n+n\log_{}{(n/m)}=O(n\log_{}{(n/m)})\]
Nếu $n=km$, $k$ là hằng số thì độ phức tạp thời gian là $O(n)$.

\subsubsection{Thuật toán song song}
Một cách đơn giản thuật toán bucket sort có thể được song song bằng cách gán mỗi bộ xử lý cho một giỏ. Khi đó, thời gian sắp xếp ở mỗi giỏ sẽ là $(n/p)\log_{}{n/p}$ với $p$ bộ xử lý (trong đó $p=m$).\\
Ta có thể cải thiện thuật toán song song trên để đạt hiệu quả hơn bằng cách phân hoạch dãy số thành $m$ miền, và mỗi miền ứng với một bộ xử lý. Mỗi bộ xử lý giữ $p$ giỏ nhỏ và tách các số trong miền của nó vào từng rỏ riêng của mình. Sau đó các giỏ nhỏ này sẽ được "chút" vào $p$ giỏ cuối cùng để sắp xếp, việc này yêu cầu mỗi bộ xử lý gửi một giỏ nhỏ tới mỗi bộ xử lý khác(giỏ thứ $i$ tới bộ xử lý thứ $i$).
\begin{figure}[!ht]
\centering
\includegraphics[scale=0.75]{bucket2.jpg}
\caption{\textit{Thuật toán bucket sort song song}}\label{fig:Hình}
\end{figure}
\paragraph{Phân tích} Thuật toán gồm 4 giai đoạn sau đây:
\begin{enumerate}
\item Phân các số vào $p$ miền.\\
Giả sử cần $n$ bước tính toán để phân $n$ số vào $p$ miền. \[t_{comp1}=n\]
Sau khi chia nhỏ, $p$ phần nhỏ mỗi phần chứa $n/p$ số được gửi tới các tiến trình.
\[t_{comm1}=t_{startup}+t_{data}n\]
\item Sắp xếp trong các giỏ nhỏ.\\
Chia mỗi phần của $n/p$ số vào $p$ giỏ nhỏ yêu cầu thời gian là \[t_{comp2}=n/p\]
\item Gửi tới các giỏ lớn.\\
Các giỏ nhỏ được phân tán. Mỗi giỏ nhỏ có khoảng $n/{p^2}$ số (giả thiết là phân bố đều). Mỗi tiến trình phải gửi $(p-1)$ giỏ nhỏ tới các tiến trình khác. Cả p tiến trình phải thực hiện phép truyền thông này, ta có \[t_{comm3}=p(p-1)(t_{startup}+(n/{p^2})t_{data})\] nếu các phép truyền thông này không thể gối nhau về thời gian và sử dụng các hàm gửi riêng . Nếu tất cả phép truyền thông được gối đầu nhau, có \[t_{comm3}=(p-1)(t_{startup}+(n/{p^2})t_{data})\]
\item Sắp xếp trong giỏ lớn.\\
Trong giai đoạn này, các giỏ lớn được sắp đồng thời, do đó \[t_{comp4}=(n/p)\log_{}{(n/p)}\]
\end{enumerate}
Vậy tổng thời gian thực hiện là
\[t_p=t_{startup}+t_{data}n+(p-1)(t_{startup}+(n/{p^2})t_{data})+(n/p)\log_{}{(n/p)}\]
Công thức trên đạt được khi các số được phân bố đều. Nếu các số không có phân bố đều thì số các số trong mỗi giỏ sẽ khác nhau, điều này sẽ làm tăng tổng thời gian tính toán. Trường hợp tồi nhất của bài toán là khi tất cả các số cùng nằm trong một giỏ.


\subsubsection{Bài toán N-vật thể}
Bài toán $N$-vật thể quan tâm tới các lực giữa các thể hay các hạt trong không gian. Mỗi một cặp các hạt này sinh ra một lực nào đó, vì vậy ta giả sử có $N$ hạt thì mỗi một hạt sẽ chịu tác động của $N-1$ lực khác nhau, $N-1$ lực này tổng hợp lại tạo thành một lực tổng hợp. Hợp lực này làm tăng tốc của hạt.\\
Bài toán $N$-vật thể có thể được định nghĩa như sau: Trong một hệ thống gồm nhiều vật thể, giả sử ta đã biết trạng thái ban đầu của tất cả các vật thể trong hệ thống, ví dụ như vận tốc và vị trí ban đầu. Ta phải đánh giá tất cả các lực tương tác giữa các vật thể để nhận được vận tốc mới và vị trí mới của các vật thể trong hệ thống. Vì vậy, bằng việc thực hiện lặp lại các đánh giá này chúng ta có được thông tin về sự biến đổi theo thời gian của hệ thống.\\
Bài toán $N$-vật thể xuất hiện trong việc nghiên cứu lý thuyết cấu trúc quy mô lớn như vũ trụ, các thiên hà, các chùm sao, hệ mặt trời, các động lực học tinh tế, mô hình khí hậu, khí đốt, chất lỏng và plasma; trong các quy mô nhỏ hơn như các hiệu ứng lượng tử. Bài toán $N$-vật thể cũng được ứng dụng trong việc mô phỏng các phân tử sinh vật lớn như sự mở ra của protein hiện thực và axit deoxyribonucleic(DNA).\\ 
Dưới đây chúng ta xem xét bài toán $N$-vật thể vô cùng lớn (các hành tinh) tác động lên nhau bởi lực hấp dẫn
\[F=\frac{G{m_a}{m_b}}{r^2}\]
trong đó, $m_a, m_b$ là khối lượng của hai vật thể\\
\hspace*{2cm} $G$ là hằng số hấp dẫn\\
\hspace*{2cm} $r$ là khoảng cách giữa hai vật thể\\
 Các vật thể trong hệ thống chuyển động với gia tốc là \[a=\frac{F}{m}\] 
trong đó, $F$ là tổng hợp lực tác động vào vật, $m$ là khối lượng của vật, $a$ là gia tốc. Vì vậy tại mỗi thời điểm khác nhau vật sẽ có một vị trí mới và một vận tốc mới. Ta biểu diễn lại công thức định luật Newton theo vận tốc của vật: \[F=m\frac{dv}{dt}\] và \[v=\frac{dx}{dt}\] trong đó, $v$ là vận tốc của vật.\\
\indent Để mô phỏng số cho bài toán ta sử dụng các giá trị thời gian cụ thể như $t_0, t_1, t_2,\ldots$, khoảng thời gian càng ngắn càng đạt được kết quả chính xác.\\
Gọi khoảng thời gian là $\Delta t$, khối lượng của vật thể là $m$ khi đó ta có:
\[F=\frac{m(v^{t+1}-v^t)}{\Delta t} \Rightarrow v^{t+1}=v^t+\frac{F\Delta t}{m}\] trong đó, $v^t, v^{t+1}$ là vận tốc của vật thể tại thời điểm $t, t+1$ tương ứng.\\
Giả sử vật thể di chuyển với vận tốc $v$ trong suốt khoảng thời gian $\Delta t$, thì vị trí của nó tại thời điểm $t+1$ là: \[x^{t+1}=x^t+v\Delta t\] trong đó, $x^t$ là vị trí tại thời điểm $t$.\\
Khi vật thể di chuyển tới vị trí mới, lực tác dụng lên nó thay đổi và quá trình tính toán được lặp lại.\\
Vì các vật thể nằm trong không gian 3-chiều nên mọi vị trí của vật thể được biểu diễn theo 3 hướng x, y và z. Khoảng cách giữa hai vật thể có khối lượng $m_a, m_b$ có vị trí tương ứng là $(x_a,y_a,z_a)$ và $(x_b, y_b, z_b)$ được tính bằng công thức: \[r=\sqrt{(x_b-x_a)^2+(y_b-y_a)^2+(z_b-z_a)^2}\]
Lực biểu diễn theo ba hướng như sau:
\[F_x=\frac{Gm_a m_b}{r^2} \biggl (\frac{x_b-x_a}{r}\biggl)\]
\[F_y=\frac{Gm_a m_b}{r^2} \biggl (\frac{y_b-y_a}{r}\biggl)\]
\[F_z=\frac{Gm_a m_b}{r^2} \biggl (\frac{z_b-z_a}{r}\biggl)\]

\subsubsection{Thuật toán tuần tự}
Thuật toán tuần tự cho bài toán N-vật thể với lực hấp dẫn được thể hiện như sau\\
1.\quad for$(t=0;t<tmax;t++)$\\
2.\qquad for$(i=0; i<N; i++)$ \{\\
3.\hspace{2cm} $F=Force_routine(i)$;\\
4.\hspace{2cm} $v[i]_new=v[i]+F*dt$;\\
5.\hspace{2cm} $x[i]_new=x[i]+v[i]_new*dt$;\\
6.\qquad \}\\
7.\quad for$(i=0; i<Nmax; i++)$ \{\\
8.\qquad $x[i]=x[i]_new$;\\
9.\qquad $v[i]=v[i]_new$;\\
10.\quad \}\\
Thuật toán yêu cầu $(N^2)$ phép tính. Giả sử chúng ta cần xác định vị trí của các vật thể trong vũ trụ, giả thiết có $10^{11}$ vật thể, nó cần lặp lại $10^{22}$ phép tính. Nếu máy tính thời gian xử lý một phép toán của máy tính tuần tự là $1\mu s$ thì mất khoảng $10^9$ năm để lặp lại một quá trình tính toán.\\
Để giảm số lượng các vật thể trong tổng lực, chúng ta có thể sử dụng quan sát sau: một khối các vật thể ở xa có thể được xấp xỉ bằng một vật thể đơn có khối lượng bằng tổng của tất cả các vật thể trong khối và có tâm đặt tại tâm của khối.
\begin{figure}[h]
\centering
\includegraphics{cluster.jpg}
\caption{\textit{Xấp xỉ khối các vật thể bằng một vật thể đơn}}\label{fig:Hình}
\end{figure}
Dưới đây ta sẽ nghiên cứu và đánh giá thuật toán song song cho bài toán N-vật thể trong không gian.
\subsubsection{Thuật toán song song}


